INSTITUTO SUPERIOR DE ECONOMIA E GESTÃO

MAEG – Investigação Operacional II – PERT-CPM

______________________________________________________________________

Exemplo Protótipo (adaptado de Hillier and Lieberman, in Introduction to Operations Research, seventh edition, pag. 469). A RELIABLE CONSTRUCTION COMPANY acaba de ganhar por $5,4 milhões um concurso para a construção de uma fábrica para uma grande empresa industrial. O dono da obra precisa da fábrica pronta no prazo de um ano. Do contracto, entre outras, fazem parte as seguintes cláusulas:

Uma penalidade de $300 000 se a RELIABLE não entregar a obra pronta no prazo de 47 semanas a partir da assinatura do contracto;

Um incentivo a uma entrega mais rápida, estando previsto um bónus de $150 000 se a obra for entre no prazo de 40 semanas.

Como director responsável pela obra foi nomeado o engenheiro David Perty, cuja principal missão será entregar a obra no prazo de 47 semanas, ou menos, com o orçamento de custos que consta da proposta. Como ele, por enquanto, tem dúvidas da possibilidade de realizar a obra em 40 semanas sem incorrer em custos excessivos, vai focalizar-se no seu plano inicial de 47 semanas.

O director vai inicialmente concentrar-se na constituição da equipa (supervisores) para com ele gerir as diferentes actividades da construção da fábrica. O quadro abaixo indica a lista das várias actividades, relação entre elas, e respectivas durações.

Lista das Actividades

Actividade	Descrição	Antecessora Imediata	Duração estimada
A	Terraplanagens	-	2 Semanas
B	Fundações	A	4 Semanas
C	Paredes	B	10 Semanas
D	Telhado	C	6 Semanas
E	Canalização exterior	C	4 Semanas
F	Canalização interior	E	5 Semanas
G	Tapume exterior	D	7 Semanas
H	Pintura exterior	E, G	9 Semanas
I	Electrificação	C	7 Semanas
J	Revestimento das paredes	F, I	8 Semanas
K	Revestimento do chão	J	4 Semanas
L	Pintura interior	J	5 Semanas
M	Suportes e Iluminação exteriores	H	2 Semanas
N	Suportes e Iluminação interiores	K, L	6 Semanas

Para programar as actividades o Sr. Perty reúne com os respectivos supervisores, pretendendo conhecer as durações estimadas para as diversas actividades. Essas estimativas encontram-se na última coluna do quadro anterior.

Tendo em conta a informação disponibilizada, o Sr. Perty pretende ter respostas para as seguintes questões:

Como pode o projecto ser representado graficamente para visualizar a sequência e relação entre as actividades?;

Qual o tempo necessário para realizar o projecto assumindo que não se verifica qualquer atraso?;

Quando é que individualmente as actividades podem (o mais cedo) ser iniciadas e (o mais tarde) terminadas?;

Quais as actividades que não podem sofrer atrasos sob pena de comprometerem a data de finalização do projecto?;

Para as outras actividades, para cada uma delas qual o atraso máximo que pode ser tolerado sem comprometer (atrasar) o projecto?;

Qual o atraso máximo que cada uma actividade pode ter sem comprometer a data mais cedo dos acontecimentos seguintes?;

Qual o atraso máximo que cada actividade pode ter supondo que as imediatamente precedentes já se atrasaram o máximo permitido, embora sem alterar a data de finalização do projecto?;

Qual a margem de cada actividade supondo que as precedentes se concluíram na data mais tarde e as seguintes são iniciadas na sua data mais cedo?;

Para visualizar a evolução do projecto, o Sr. Perty pretende estabelecer um calendário (Time Schedule) do projecto;

Sabendo que há incerteza na realização das actividades e os supervisores apresentaram estimativas optimistas, mais prováveis e pessimistas, dadas pelo quadro abaixo, qual a probabilidade de o projecto ser cumprido na data estabelecida em contrato? Comente;

Durações Estimadas das Actividades (em semanas)

Actividade	Duração Optimista	Duração Mais Provável	Duração Pessimista
A	1	2	3
B	2	3,5	8
C	6	9	18
D	4	5,5	10
E	1	4,5	5
F	4	4	10
G	5	6,5	11
H	5	8	17
I	3	7,5	9
J	3	9	9
K	4	4	4
L	1	5,5	7
M	1	2	3
N	5	5,5	9

Admitindo que se dispõe de um orçamento de custos adicionais, qual o montante mínimo a gastar de modo a completar o projecto em 40 semanas, considerando a informação do quadro abaixo?;

Admitindo que o dono da obra em vez do bónus associado à realização do projecto em 40 semanas propõe uma solução mais flexível, que consiste em estabelecer um bónus de $25 000 por cada semana de antecipação em relação à data de 47 semanas, para que prazo deve ser programada a obra, considerando a informação do quadro abaixo?

Custos de Aceleração nas Actividades
Duração (semanas)	Custo ($ mil)
Actividades	Normal	Acelerada	Normal	Acelerado
A	2	1	180	280
B	4	2	320	420
C	10	7	620	860
D	6	4	260	340
E	4	3	410	570
F	5	3	180	260
G	7	4	900	1020
H	9	6	200	380
I	7	5	210	270
J	8	6	430	490
K	4	3	160	200
L	5	3	250	350
M	2	1	100	200
N	6	3	330	510

2.	(Exemplo 6.5-1, TAHA, pag.278) Um editor tem um contrato com um autor para publicar um livro. As actividades (simplificadas) associadas à produção do livro encontram-se descritas abaixo. O autor deverá submeter à apreciação do editor uma cópia e um ficheiro de computador do respectivo manuscrito.

Represente a rede do projecto e determine a respectiva duração, identificando o caminho crítico.

Actividade	Duração (Semanas)	Predecessora
A Leitura do Manuscrito	3	-
B Preparação do tipo de Páginas	2	-
C Design da Capa	4	-
D Preparação do Trabalho Artístico	3	-
E Aprovação do Manuscrito e tipo Páginas	2	A, B
F Formatação do Livro	4	E
G Revisão pelo Autor da Formatação	2	F
H Revisão pelo Autor do Trabalho Artístico	1	D
I Produção das Chapas de Impressão	2	G, H
J Produção e Encadernação do Livro	4	C, I

Considere um projecto de construção de um parque industrial cujas actividades são as seguintes:

Actividade: A B C D E F G H I J L M

Ant.Imed. - - - A,B,C B,C B,C C D,E,F,G D,E,F,G FG I,J H,I,J

Estabeleça a rede, com actividades nos arcos, deste projecto com um mínimo de actividades fictícias.

4.	Considere-se um projecto de construção de um edifício que envolve as seguintes actividades:

Actividade	Duração (Dias)	Predecessora
A Escavações	2	-
B Fundações	4	A
C Paredes	10	B
D Canalizações Exteriores	4	C
E Telhado	6	C
F Reboco	7	E
G Pintura Exterior	9	D, F
H Canalizações Interiores	5	D
I Electrificação	7	C
J Revestimento Interior	8	H, I
K Equipamentos Exteriores	2	G
L Colocação do Soalho	4	J
M Pintura interior	5	J
N Equipamentos Interiores	6	L, M

Representar numa rede de projecto as actividades e as suas relações de precedência. Determine a respectiva duração, identificando o caminho crítico.

5.	Considere um projecto constituído pelas actividades A, B, …, H cujas durações e relações de precedência são as indicadas na tabela. Admita ainda que não possível iniciar a actividade G antes de decorrerem 3 dias sobre o início da actividade F e que a actividade E não pode ter início antes de decorridos 2 dias sobre o fim das suas predecessoras.

Determine a duração mínima do projecto, as actividades críticas e as margens para todas as actividades.

Actividade	Duração (Dias)	Predecessora
A	10	-
B	15	A
C	12	B
D	13	B
E	4	C, D
F	8	C
G	7	C
H	17	G

6.	A rede que se apresenta de seguida diz respeito a um projecto, para o qual se pode considerar que os tempos de execução das tarefas são variáveis aleatórias normais e independentes, cujos valores esperados e variâncias são os indicados sob cada arco da rede (valor esperado; desvio padrão).

1 2 5 4 6 7 8 A(10; 4) D(5; 1) B(14; 10) C(8; 5) 3 G(10; 5) E(10; 6) F(10; 5) H(5; 1) f f f f

Indique, justificando, as actividades sobre as quais é sensato tomar mais atenção;

Determine a probabilidade do tempo de execução do caminho {(1,2); (2,4); (4,5); (5,8)} ser superior ao tempo de execução do caminho {(1,2); (2,4); (4,5); (5,6); (6,8)}.

7.	Considere um projecto constituído pelas actividades A a H, com as seguintes características:

Actividade	(i,j)	(aij,mij,bij)
A	(1,2)	(3,5,7)
B	(1,3)	(4,6,8)
C	(2,3)	(1,3,5)
D	(2,4)	(5,8,11)
E	(3,5)	(1,2,3)
F	(3,6)	(9,11,13)
G	(4,6)	(1,1,1)
H	(5,6)	(10,12,14)

e em que a actividade D precede as actividades G e H.

a)	Calcule a duração esperada do projecto;

b)	Para cada acontecimento j, determine a probabilidade de j ocorrer até à data Sj a seguir indicada, isto é, calcule P[ej ≤ Sj], com

j	2	3	4	5	6
Sj	5	11	12	14	26

8.	Considere um pequeno projecto cujas actividades principais, durações e relações de precedência, são as seguintes:

Durações
Actividades	Precedentes	Optimista	Mais provável	Pessimista
A	-	25	28	43
B	-	38	52	54
C	-	35	40	45
D	A	24	29	40
E	B, G	17	19	27
F	C	35	40	75
G	A	35	40	45

Determine a duração esperada do projecto e a sua variância;

Qual a probabilidade da duração do projecto ser não superior a 95 dias?;

Qual o prazo de realização que se poderá cumprir com probabilidade de 99%?;

Qual a probabilidade de C e F durarem, em conjunto, mais do que o caminho crítico?

9.	Considere um projecto, cujas actividades, durações (em dias), relações de precedência, acelerações máximas e custos unitários de aceleração são as seguintes:

Actividade	Act. Precedente	Duração normal	Aceleração máxima	C.U. Aceleração
A	-	35	10	5
B	-	42	12	4
C	A	21	7	6,5
D	A	56	15	6
E	B, C	14	4	8
F	B, C	77	20	4,5
G	D	7	3	7,5
H	D, E	84	20	5

Determine o caminho crítico, considerando as durações normais indicadas;

Formule o problema com problema de Programação Linear e resolva-o através de um dos “softwares” conhecidos;

Acha que é possível executar o projecto em menos 25 dias de duração do que a que decorre das durações normais? Se sim, quais os custos adicionais para conseguir esta redução?;

Suponha que por cada dia de antecipação se tem um prémio de 10 u.m.. Determine a duração óptima.

10.	Considere um projecto de construção de um edifício cujas principais tarefas são as que se encontram na tabela seguinte. Com base nas relações de precedência aí exibidas:

Determine a duração do projecto;

Indique as actividades críticas e o caminho crítico;

Calcule as margens livres e totais para cada uma das actividades não críticas;

Tendo em conta o número de trabalhadores necessários para realizar cada uma das tarefas e admitindo que os trabalhadores estão aptos para executar qualquer tarefa, apresente uma calendarização que lhe permita ter, em cada momento, não mais do que seis trabalhadores no edifício.

Tarefas	Tarefas sucessoras	Duração (semanas)	Nº de trabalhadores
A	Fundações	B	5	5
B	Estrutura	C, I	8	6
C	Paredes	D, G, H, L	14	3
D	Tecto	E	10	3
E	Telhado	-	3	4
F	Pinturas	J	31	2
G	Instalação eléctrica	F, J	11	2
H	Condutas	F, M	10	3
I	Soalhos	J	9	3
J	Acabamentos interiores	-	3	4
L	Acabamentos exteriores	-	10	4
M	Sanitários	J	5	1